package 每日一题;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 919. 完全二叉树插入器
 * 完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。
 *
 * 设计一种算法，将一个新节点插入到一个完整的二叉树中，并在插入后保持其完整。
 *
 * 实现 CBTInserter 类:
 *
 * CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构；
 * CBTInserter.insert(int v)  向树中插入一个值为 Node.val == val的新节点 TreeNode。使树保持完全二叉树的状态，并返回插入节点 TreeNode 的父节点的值；
 * CBTInserter.get_root() 将返回树的头节点。
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入
 * ["CBTInserter", "insert", "insert", "get_root"]
 * [[[1, 2]], [3], [4], []]
 * 输出
 * [null, 1, 2, [1, 2, 3, 4]]
 *
 * 解释
 * CBTInserter cBTInserter = new CBTInserter([1, 2]);
 * cBTInserter.insert(3);  // 返回 1
 * cBTInserter.insert(4);  // 返回 2
 * cBTInserter.get_root(); // 返回 [1, 2, 3, 4]
 *
 *
 * 提示：
 *
 * 树中节点数量范围为 [1, 1000]
 * 0 <= Node.val <= 5000
 * root 是完全二叉树
 * 0 <= val <= 5000
 * 每个测试用例最多调用 insert 和 get_root 操作 104 次
 */
public class D220725_T0919 {
     static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }


    class CBTInserter {

        private final TreeNode root;
        private final ArrayList<TreeNode> list; //层序遍历
        private int insert_index; //上一次修改节点的坐标

        public CBTInserter(TreeNode root) {
            this.root = root;
            Queue<TreeNode> queue = new LinkedList<>();
            list = new ArrayList<>();
            queue.add(root);
            while (!queue.isEmpty()){
                TreeNode node = queue.poll();
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
                list.add(node);
            }
            //找到list中 第一个子节点存在null的坐标
            for (int i = 0; i < list.size(); i++) {
                TreeNode treeNode = list.get(i);
                if (treeNode.left==null||treeNode.right==null){
                    insert_index = i;
                    break;
                }
            }

        }


        public int insert(int val) {

            TreeNode treeNode = new TreeNode(val);
            list.add(treeNode);
            TreeNode treeNodeFather = list.get(insert_index);
            if (treeNodeFather.left==null) {
                treeNodeFather.left = treeNode;
            }else {
                treeNodeFather.right = treeNode;
                insert_index++;
            }

            return treeNodeFather.val;
        }

        public TreeNode get_root() {
            return root;
        }


    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        CBTInserter cbtInserter = new D220725_T0919().new CBTInserter(root);
        cbtInserter.insert(3);
        cbtInserter.insert(4);
    }
}
